package array.removeElement;

/**
 * 给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
 * <p>
 * 注意：如果对空文本输入退格字符，文本继续为空。
 */
public class N844_BackspaceCompare {
    /**
     * 构建字符串
     */
    public boolean backspaceCompare_StringBuilder(String s, String t) {
        return build(s).equals(build(t));
    }

    private String build(String str) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            if (ch != '#') {
                sb.append(ch);
            } else {
                if (sb.length() > 0) {
                    sb.deleteCharAt(sb.length() - 1);
                }
            }
        }
        return sb.toString();
    }

    /**
     * 双指针法
     */
    public boolean backspaceCompare_doubleIndex(String s, String t) {
        // 从后往前开始遍历
        int i = s.length() - 1, j = t.length() - 1,
                // #计数器，计算当前#可以忽略前面多少个字符
                skipS = 0, skipT = 0;
        while (i >= 0 || j >= 0) {
            // 找到s字符串需要比较的字符
            while (i >= 0) {
                if (s.charAt(i) == '#') {
                    skipS++;
                    i--;
                } else if (skipS > 0) {
                    skipS--;
                    i--;
                } else {
                    break;
                }
            }
            // 找到t字符串需要比较的字符
            while (j >= 0) {
                if (t.charAt(j) == '#') {
                    skipT++;
                    j--;
                } else if (skipT > 0) {
                    skipT--;
                    j--;
                } else {
                    break;
                }
            }
            // 如果两个字符串指针都还是合法的
            if (i >= 0 && j >= 0) {
                // 比较当前两个指针指向的字符是否相等
                if (s.charAt(i) != t.charAt(j)) {
                    return false;
                }
            } else {
                // 其中有一个或两个字符串指针非法，则判断是否有一个是还有剩余未比较的字符。
                // 也就是说可能有一个扫描完了，另一个还有剩下的未扫描，则直接返回false了
                if (i >= 0 || j >= 0) {
                    return false;
                }
            }
            i--;
            j--;
        }
        // 扫描完两个字符串，没有问题就是返回true了
        return true;
    }

    public static void main(String[] args) {
        N844_BackspaceCompare solution = new N844_BackspaceCompare();
        String s = "ab#", t = "ab#";
        System.out.println(solution.backspaceCompare_StringBuilder(s, t));
        System.out.println(solution.backspaceCompare_doubleIndex(s, t));
    }

}
